package Luogu;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P1964 {
    static class good {
        int piece;
        int value;
        int lagerNum;
        String name;

        public good(int piece, int value, int lagerNum, String name) {
            this.piece = piece;
            this.value = value;
            this.lagerNum = lagerNum;
            this.name = name;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String tmp = br.readLine();
        int usedV = Integer.parseInt(tmp.split(" ")[0]);

        int V = 21 - usedV;
        int n = Integer.parseInt(tmp.split(" ")[1]);
        good[] goods = new good[n + 1];
        for (int i = 1; i <= n; i++) {
            tmp = br.readLine();
            String[] elements = tmp.split(" ");
            goods[i] = new good(Integer.parseInt(elements[0]), Integer.parseInt(elements[1]),
                    Integer.parseInt(elements[2]), elements[3]);

            for (int j = 0; j <= i; j++) {
                if (i!=j && goods[j] != null &&goods[j].name .equals(goods[i].name)) {
                    if (goods[j].piece + goods[i].piece <= goods[i].lagerNum) {
                        goods[j].piece += goods[i].piece;
                        i--;
                        n--;
                    } else {
                        goods[i].piece -= goods[i].lagerNum - goods[j].piece;
                        goods[j].piece = goods[j].lagerNum;
                    }
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            goods[i].value *= goods[i].piece;
        }
        long[][] dp = new long[n + 1][V + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= V; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + goods[i].value);
            }
        }
        System.out.println(dp[n][V]);

    }
}
